package 力扣_简单题;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 连安利
 * @version 1.0
 * @date 2021/3/24 20:37
 */

public class 数组中重复的数字 {
    public static void main(String[] args) {
        int num[] ={3, 3, 2, 1, 6, 2, 5, 3};
//        System.out.println(findRepeatNumber(num));
        System.out.println(findRepeatNumber2(num));
    }
    public static int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;

        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
    public static int findRepeatNumber2(int[] nums) {
//        原地置换
        int temp;
        for(int i = 0; i < nums.length; i++){
            while (nums[i] != i){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                temp = nums[i];
                nums[i] = nums[nums[i]];
                nums[temp] = temp;
            }
        }
        return 0;
    }
}
